MNF130 - Diskrete strukturar (Gruppe 3 og 9)

Injective and surjective functions

Let f\colon X\to Y$f\colon X\to Y$ be a function. Then f$f$ is

• injective (or one-to-one) if no two elements in X$X$ map to the same element under f$f$. Or in other words, if x\neq y$x\neq y$ then f(x)\neq f(y)$f(x)\neq f(y)$.
• surjective (or onto) if all elements in Y$Y$ are hit by f$f$. That is, for all y\in Y$y\in Y$ there exists some x\in X$x\in X$ such that f(x)=y$f(x)=y$.
• bijective if f$f$ is both injective and surjective.

Some set operations visualized with Venn diagrams

There are many ways to do this. Don't worry if your solution is different from the proposed one.

General tips:
- Do you see a pattern or some property all elements in the set share?
- Can you describe this property using symbols?

For example, the set S=\{1,4,9,16,25,36\}$S=\{1,4,9,16,25,36\}$ consists of the squares 1^2, 2^2, 3^2, 4^2, 5^2, 6^2$1^2, 2^2, 3^2, 4^2, 5^2, 6^2$ so we can write S$S$ as follows using set builder notation:

S=\{n^2\mid n\in\mathbb{Z} \wedge (1\leq n\leq 6)\}

a) Here are three possible ways to do it:

• \{3n\mid n\in\mathbb{Z}\wedge 0\leq n\leq4\}$\{3n\mid n\in\mathbb{Z}\wedge 0\leq n\leq4\}$
• \{n\in\mathbb{Z}\mid n=3k\text{ for } k\in\{0,1,2,3,4\}\}$\{n\in\mathbb{Z}\mid n=3k\text{ for } k\in\{0,1,2,3,4\}\}$.
• \{n\in\mathbb{Z}\mid n\text{ is non-negative, smaller than }13\text{ and is divisible by }3\}$\{n\in\mathbb{Z}\mid n\text{ is non-negative, smaller than }13\text{ and is divisible by }3\}$.

b) \{n\in\mathbb{Z}\mid -3\leq n\leq 3\}$\{n\in\mathbb{Z}\mid -3\leq n\leq 3\}$

c) There is no clearly obvious way to do this. But let's try something:

• Let A$A$ denote the set of lower-case letters in the latin alphabet. That is, A=\{a,b,c,d,e,\ldots,w,x,y,z\}$A=\{a,b,c,d,e,\ldots,w,x,y,z\}$.
• Now, let's introduce an ordering on the elements in A$A$ as follows: for \alpha,\beta\in A$\alpha,\beta\in A$ define the ordering <$<$ by letting \alpha<\beta$\alpha<\beta$ if and only if \alpha$\alpha$ comes before \beta$\beta$ in the alphabet. (Remember, a set has no ordering of it elements. But, we are imposing one on A$A$ now.)
• For example, if \alpha=c$\alpha=c$ and \beta=a$\beta=a$, then \beta<\alpha$\beta<\alpha$ since a$a$ comes before b$b$ in the alphabet.
• Using our ordered set of letters, we can use set builder notation to complete the task \{m,n,o,p\} = \{\alpha\in A\mid l<\alpha<q\}$\{m,n,o,p\} = \{\alpha\in A\mid l<\alpha<q\}$.

Rememeber that every element in a set is unique. So for example, \{a,a,b,c\} = \{a,b,c\}$\{a,a,b,c\} = \{a,b,c\}$. Sets cannot encode duplicates! (If you want to do this, you can look up the notion of multisets. But this is probably not a part of this course.)

Also, sets don't care about the order of elements. For example, \{a,b,c\} = \{b,a,c\}$\{a,b,c\} = \{b,a,c\}$.

Note that the set containing a$a$ is not the same as a$a$. That is, \{a\}\neq a$\{a\}\neq a$.

a) Yes they are the same set.
b) They are not equal.
c) They are not equal. The set \emptyset$\emptyset$ contains no elements. However, the set \{\emptyset\}$\{\emptyset\}$ contains the element \emptyset$\emptyset$.

For a set A$A$ to be a subset of another set B$B$ (written A\subseteq B$A\subseteq B$, or A\subset B$A\subset B$) it is sufficient and necessary that for all elements a$a$ in A$A$, a$a$ is also in B$B$. Symbolically, that is A\subseteq B \iff \forall a (a\in A\implies a\in B)$A\subseteq B \iff \forall a (a\in A\implies a\in B)$.

If the set A$A$ has strictly more elements than B$B$, then there is no way A$A$ can be a subset of (or equal to) B$B$. This restricts the number of inclusions you have to check.

For every set A$A$, we have A\subseteq A$A\subseteq A$ but this is not interesting.

We only have to check the following inclusions:

1. B\subseteq A$B\subseteq A$ True
2. C\subseteq A$C\subseteq A$ True
3. D\subseteq A$D\subseteq A$ False, 8\in D$8\in D$ but 8\notin A$8\notin A$
4. A\subseteq D$A\subseteq D$ False
5. B\subseteq D$B\subseteq D$ False
6. C\subseteq D$C\subseteq D$ True
7. B\subseteq C$B\subseteq C$ False
8. C\subseteq B$C\subseteq B$ False

Step 0: Try some examples:

Step 1: Guess some hypothesis!

• If A\times B=\emptyset$A\times B=\emptyset$, what can we say about A$A$ and B$B$?
• For (most types of) numbers a$a$ and b$b$, recall that ab=0$ab=0$ implies that a=0$a=0$ or b=0$b=0$. This exercise is somehow the analogue where we have replaced numbers with sets.

Step 2: Prove your hypothesis!

• Try using the definition of the cartesian product A\times B=\{(a,b)\mid a\in A\wedge b\in B\}$A\times B=\{(a,b)\mid a\in A\wedge b\in B\}$ and give a direct proof.
• OR
• Think about what you can say about A\times B$A\times B$ if A$A$ and B$B$ both contain at least one element.

By the definition of ordered pairs given in the exercise, we have (a,b)=\{\{a\},\{a,b\}\}$(a,b)=\{\{a\},\{a,b\}\}$ and (c,d)=\{\{c\},\{c,d\}\}$(c,d)=\{\{c\},\{c,d\}\}$. Let us write A=(a,b)$A=(a,b)$ and C=(c,d)$C=(c,d)$ to keep things simple. We need to show that A=C\iff (a=c\wedge b=d)$A=C\iff (a=c\wedge b=d)$. We can split the proof into two parts. Namely,

1. A=C\implies (a=c\wedge b=d)$A=C\implies (a=c\wedge b=d)$ and
2. (a=c\wedge b=d)\implies A=C$(a=c\wedge b=d)\implies A=C$.

The implication (2) is easy: if a=c$a=c$ and b=d$b=d$, then A=\{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}=C$A=\{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}=C$ so we are done.

Now, try to give a convincing argument for (1). That is, argue why \{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}$\{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}$ implies that a=c$a=c$ and b=d$b=d$. What does it mean for sets to be equal? And how can we check it?

Try to consider the two possible cases a=b$a=b$ and a\neq b$a\neq b$. If a=b$a=b$ then \{\{a\},\{a,b\}\} = \{\{a\},\{a,a\}\} = \{\{a\},\{a\}\} = \{\{a\}\}$\{\{a\},\{a,b\}\} = \{\{a\},\{a,a\}\} = \{\{a\},\{a\}\} = \{\{a\}\}$.

a) A\cup B$A\cup B$ consists of all elements that are contained in A$A$ or B$B$ (or both).
b) A\cap B$A\cap B$ consists of all elements that are both in A$A$ and B$B$.
c) and d) A\setminus B = A-B$A\setminus B = A-B$ contains all elements of A$A$ that are not contained in B$B$.

a) \{0,1,2,3,4,5,6\}$\{0,1,2,3,4,5,6\}$
b) \{3\}$\{3\}$
c) \{1,2,4,5\}$\{1,2,4,5\}$
d) Similar to (c).

One way of proving this is to write both sides of the equality symbol using set builder notation and then (hopefully) realize that the two sides represents the same thing.

Recall the following definitions:

• A-B = \{x\mid x\in A\wedge x\notin B\}$A-B = \{x\mid x\in A\wedge x\notin B\}$
• \bar{A} = \{x\mid x\notin A\}$\bar{A} = \{x\mid x\notin A\}$
• A\cap B = \{x\mid x\in A\wedge x\in B\}$A\cap B = \{x\mid x\in A\wedge x\in B\}$
• A\cup B = \{x\mid x\in A\vee x\in B\}$A\cup B = \{x\mid x\in A\vee x\in B\}$

Another way is to show that the left-hand side is contained in the right-hand side, and the other way around.

You could also try to use a Venn diagram, or use some set identities you know.

b) (A\cap B)\cup(A\cap\bar{B}) = \{x\mid (x\in A\wedge x\in B)\vee (x\in A \wedge x\notin B) \} = \{x\mid (x\in A)\wedge(x\in B \vee x\notin B) \} = \{x\mid (x\in A)\wedge\textbf{T} \}=\{x\mid x\in A\} = A$(A\cap B)\cup(A\cap\bar{B}) = \{x\mid (x\in A\wedge x\in B)\vee (x\in A \wedge x\notin B) \} = \{x\mid (x\in A)\wedge(x\in B \vee x\notin B) \} = \{x\mid (x\in A)\wedge\textbf{T} \}=\{x\mid x\in A\} = A$

1. Write it out. For example, if A_i=(0,i)$A_i=(0,i)$, then we can write \bigcup_{i=1}^\infty A_i = \bigcup_{i=1}^\infty(0,i) = (0,1)\cup(0,2)\cup(0,3)\cup\ldots\cup(0,i)\cup\ldots$\bigcup_{i=1}^\infty A_i = \bigcup_{i=1}^\infty(0,i) = (0,1)\cup(0,2)\cup(0,3)\cup\ldots\cup(0,i)\cup\ldots$.
2. Remember: an element x$x$ is in \bigcup_{i=1}^\infty A_i$\bigcup_{i=1}^\infty A_i$ if and only if x$x$ is contained in at least one of the A_i$A_i$'s for some value of i$i$.
3. Remember: an element x$x$ is in \bigcap_{i=1}^\infty A_i$\bigcap_{i=1}^\infty A_i$ if and only if x$x$ is contained in A_i$A_i$ for ALL values of i=1,2,3,4,\ldots$i=1,2,3,4,\ldots$
4. Maybe it can be helpful to visualize/draw it?

a)

\begin{align*}
\bigcup_{i=1}^\infty A_i &= \bigcup_{i=1}^\infty\{i,i+1,i+2,\ldots,\} = \{1,2,3,4,\ldots\}\cup\{2,3,4,5\ldots\}\cup\ldots = \{1,2,3,4,5,6,\ldots\} = \{n\in\mathbb{Z}\mid n>0\}\\
\bigcap_{i=1}^\infty A_i &= \bigcap_{i=1}^\infty\{i,i+1,i+2,\ldots,\} = \{1,2,3,4,\ldots\}\cap\{2,3,4,5\ldots\}\cap\ldots = \emptyset
\end{align*}

The last one (intersection): if n\in\bigcap_{i=1}^\infty A_i$n\in\bigcap_{i=1}^\infty A_i$ then n\in A_i$n\in A_i$ for all choices of i$i$. Choose i=n+1$i=n+1$, then n\in A_{n+1} = \{n+1, n+2, n+3,\ldots\}$n\in A_{n+1} = \{n+1, n+2, n+3,\ldots\}$ which is clearly not true. Hence, there are exists not n$n$ such that n\in\bigcap_{i=1}^\infty A_i$n\in\bigcap_{i=1}^\infty A_i$ which means it is the empty set.

b)

\begin{align*}
\bigcup_{i=1}^\infty A_i &= \bigcup_{i=1}^\infty\{0,i\} = \{0,1\}\cup\{0,2\}\cup\{0,3\}\cup\ldots = \{0,1,2,3,4,\ldots\}= \{n\in\mathbb{Z}\mid n\geq 0\}\\
\bigcap_{i=1}^\infty A_i &= \bigcap_{i=1}^\infty\{0,i\} = \{0,1\}\cap\{0,2\}\cap\{0,3\}\cap\ldots = \{0\}
\end{align*}

c)

\begin{align*}
\bigcup_{i=1}^\infty A_i &= \bigcup_{i=1}^\infty(0,i) = (0,1)\cup(0,2)\cup(0,3)\cup\ldots\cup(0,i)\cup\ldots = (0,\infty) = \{x\in \mathbb{R}\mid x>0\}\\
\bigcap_{i=1}^\infty A_i &= \bigcap_{i=1}^\infty(0,i) = (0,1)\cap(0,2)\cap(0,3)\cap\ldots\cap(0,i)\cap\ldots = (0,1)
\end{align*}

d)

\begin{align*}
\bigcup_{i=1}^\infty A_i &= \bigcup_{i=1}^\infty(i,\infty) = (1,\infty)\cup(2,\infty)\cup(3,\infty)\cup\ldots = (1,\infty) = \{x\in \mathbb{R}\mid x>1\}\\
\bigcap_{i=1}^\infty A_i &= \bigcap_{i=1}^\infty(i,\infty) = (1,\infty)\cap(2,\infty)\cap(3,\infty)\cap\ldots = \emptyset
\end{align*}

Explanation for the last one: Assume x$x$ is an element of \bigcap_{i=1}^\infty(i,\infty)$\bigcap_{i=1}^\infty(i,\infty)$. Then, x\in(i,\infty)$x\in(i,\infty)$ for all values of i$i$ by the definition of the intersection. But choose i$i$ to be some integer larger than x$x$ (for example, choose i=\lceil x \rceil+1$i=\lceil x \rceil+1$) and we have x\notin (i,\infty)$x\notin (i,\infty)$ which is a contradiction. Therefore, our assumption must be wrong. That is, there are no elements in \bigcap_{i=1}^\infty(i,\infty)$\bigcap_{i=1}^\infty(i,\infty)$ which means that it must be the empty set \emptyset$\emptyset$.

a) What is the definition of a function? Can a function map an element to two elements?
b) Does it satisfy what it takes to be a function \mathbb{Z}\to\mathbb{R}$\mathbb{Z}\to\mathbb{R}$?
c) Is it defined for all values in the domain \mathbb{Z}$\mathbb{Z}$?

a) No, a function f\colon A\to B$f\colon A\to B$ maps an element a\in A$a\in A$ to exaclty one element f(a)\in B$f(a)\in B$.
b) Yes this defines a function f\colon\mathbb{Z}\to\mathbb{R}$f\colon\mathbb{Z}\to\mathbb{R}$.
c) No, the expression is undefined whenever n=2$n=2$ or n=-2$n=-2$.

What is the definition of being one-to-one (injective)?
How can a function fail to be one-to-one?
Can a function that maps two or more elements to the same element be injective?

A bijection is a function that is both injective (one-to-one) and surjective (onto).

a) Yes (Check it!)
b) No (Same reason as (d). See below.)
c) Yes (Check it!)
d) No (It's always positive so it can't be surjective. Also, f(x)=f(-x)$f(x)=f(-x)$ so it's not injective either.)

Set y=ax+b$y=ax+b$ and solve for x$x$. How does this give you the inverse of f$f$?

Here is a graphical "proof" that a linear function (in one dimension) is invertible:

Writing y=ax+b$y=ax+b$ and solving for x$x$ we get x=\frac{y-b}{a}$x=\frac{y-b}{a}$. So I claim that g(y) = \frac{y-b}{a}$g(y) = \frac{y-b}{a}$ is the inverse of f$f$.

Let's check the claim:

1. f(g(y)) = f(\frac{y-b}{a}) = a\frac{y-b}{a}+b = y-b+b = y$f(g(y)) = f(\frac{y-b}{a}) = a\frac{y-b}{a}+b = y-b+b = y$ and
2. g(f(x)) = g(ax+b) = \frac{ax+b-b}{a} = \frac{ax}{a} = x$g(f(x)) = g(ax+b) = \frac{ax+b-b}{a} = \frac{ax}{a} = x$.

Indeed we have that g=f^{-1}$g=f^{-1}$.